import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Text {
    //给一个数组 和一个目标值 target 求出数组里面 四个数 加起来等于目标值的    返回这四个数 且不重复

    public List<List<Integer>> fourSum(int[] nums, int target) {
        //定义一个顺序表来接收
        List<List<Integer>> list = new ArrayList<>();
        //先排序
        Arrays.sort(nums);
        int n = nums.length;  //求一下数组的长度
        for (int i = 0; i < n;) {  //固定一个数a
            for (int j = i + 1; j < n;) {  //再固定一个数b
                //利用 双指针 算法
                int left = j + 1, right = n-1;
                long sum =(long) target - nums[j] - nums[i];  //强转 防止溢出
                while (left < right) {  //开始遍历
                    if (sum < nums[left] + nums[right]) {
                        //说明右边数比较大
                        right--;
                    }else if (sum > nums[left] + nums[right]) {
                        left++;
                    }else {
                        //相等就加到list中
                        list.add(new ArrayList<>(Arrays.asList(nums[left],nums[right],nums[j],nums[i])));
                        left++;
                        right--;   // 缩小范围
                        //去重
                        while (left < right && nums[left] == nums[left-1]) left++;
                        while (left < right && nums[right] == nums[right+1]) right--;
                    }
                }
                //对 j下标的值去重
                j++;
                while (j < n && nums[j] == nums[j-1]) j++;
            }
            //同样  对i下标的值 去重
            i++;
            while (i < n && nums[i] == nums[i-1]) i++;
        }
        //最后返回list
        return list;
    }

    //给一个数组  找出 里面三个数相加等于0 的返回  而且 下标不能重复  并且 要去重
    public List<List<Integer>> threeSum(int[] nums) {
        //定义一个list去接收
        List<List<Integer>> list = new ArrayList<>();
        //先排序
        Arrays.sort(nums);
        int n = nums.length;
        //先固定一个数  然后用双指针算法
        for (int i = 0; i < n-1;) {
            if (nums[i] > 0) break;
            //定义两个指针  和一个和
            int left = i + 1, right = n - 1, tag = -nums[i];
            while (left < right) {
              int  sum = nums[left] + nums[right];
                if (sum > tag) right--;
                else if (sum < tag) left++;
                else {
                    //相等
                    list.add(new ArrayList<Integer>(Arrays.asList(nums[left],nums[right],nums[i])));
                    left++;
                    right--;
                    //去重
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                }
            }
            //还有一个要去重  就是固定的数
            i++;
            while (i < n && nums[i] == nums[i-1]) i++;
        }
        return list;
    }
    // 给一个数组 和  一个值  返回数组中 两个数加起来等于那个值的数
    public int[] twoSum(int[] price, int target) {
        //定义两个指针
        int left = 0, right = price.length - 1;
        while (left < right) {
            int sum = price[left] + price[right];
            if (sum > target) {
                right--;
            }else if (sum < target) {
                left++;
            }else {
                return new int[]{price[left],price[right]};
            }
        }
        return new int[]{0};
    }

    //给一个数组 找出里面能组成 三角形的三元组个数

    public int triangleNumber(int[] nums) {
        //先对数组进行排序
        Arrays.sort(nums);   //可以利用单调性 来解决这道题
        int sum = 0;  //先定义一个变量来计算 个数
        int n = nums.length;  //计算一下数组的长度
        for (int i = n - 1; i >= 2 ; i--) {
            //定义两个指针
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    sum += right - left;
                    right--;
                }else {
                    left++;
                }
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] arr = {4,2,3,4};
        Text text = new Text();
       int ret =text.triangleNumber(arr);
        System.out.println(ret);
    }
}
